10224. Articulation pointsTimestamps

 

An undirected graph is given. Run a depth first search from the given vertex v. Print the timestamps d[v] and up[v] for each vertex v in the increasing order of vertices.

 

Input. The first line contains the number of vertices n (n ≤ 100) and edges m of an undirected graph. Each of the next m  lines contains two vertices a and b – an undirected edge of the graph. The last line contains vertex v.

 

Output. Run dfs(v). Print the timestamps d[v] and up[v] for each vertex v (v = 1, 2, ..., n). The timestamps for each vertex must be printed on a separate line.

 

Hint. Use the adjacency matrix to get accepted.

 

Sample input 1

Sample output 1

6 8

6 5

6 3

5 3

4 5

3 4

3 2

1 2

1 3

1

1 1

2 1

3 1

4 3

5 3

6 3

 

 

Sample input 2

Sample output 2

7 9

1 2

2 3

1 3

3 4

2 5

4 5

4 6

4 7

6 7

1

1 1

2 1

3 1

4 2

5 2

6 4

7 4

 

 

SOLUTION

graphsarticulation points

 

Algorithm analysis

The labels d[v] / up[v] are used to find articulation points. Perform a depth first search and set up the indicated labels.

 

Example

Place the labels in the graphs given in the first and second test cases.

 

Algorithm realization

Declare the adjacency matrix g and the arrays used, d and up.

 

#define MAX 101

int g[MAX][MAX];

int used[MAX], d[MAX], up[MAX];

 

Function dfs runs the depth-first search and sets up the labels d[v] and up[v].

 

void dfs(int v, int p = -1)

{

  used[v] = 1;

  d[v] = up[v] = tm++;

  for (int i = 1; i <= n; i++)

  {

    if (g[v][i] == 0) continue;

    if (i == p)  continue;

    if (used[i])

      up[v] = min(up[v], d[i]);

    else

    {

      dfs(i, v);

      up[v] = min(up[v], up[i]);

    }

  }

}

 

The main part of the program. Read the input data. Fill in the adjacency matrix of the graph g.

 

scanf("%d %d", &n, &m);

for (i = 0; i < m; i++)

{

  scanf("%d %d", &a, &b);

  g[a][b] = g[b][a] = 1;

}

 

Read the vertex v and start the depth-first search from it.

 

scanf("%d", &v);

tm = 1;

dfs(v);

 

For each vertex, print the labels d[v] and up[v].

 

for (i = 1; i <= n; i++)

  printf("%d %d\n", d[i], up[i]);